#!/usr/env/bin python
# -*- coding: utf-8 -*-
# filename: 存在重复 III.py
# creator: yangdy
# create date: 2018/3/29
"""  
存在重复 III
TODO模块说明
Public Class:
-	TODO类名: TODO类说明 
Public Methods: 
-	TODO方法名: TODO方法说明
"""
class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        from random import randint
        MAX_H = 10000
        class Tree:
            class TreeNode:
                def __init__(self, val):
                    self.val = val
                    self.right = None
                    self.left = None
                    self.n = 1
                    self.h = randint(0, MAX_H)
            def __init__(self):
                self.root = None
            def left_rotate(self, p=None):
                if not p or not p.left:
                    return
                l = p.left
                p.val, l.val = l.val, p.val
                p.n, l.n = l.n, p.n
                p.h, l.h = l.h, p.h
                p.left = l.left
                l.left = l.right
                l.right = p.right
                p.right = l
            def right_rotate(self, p=None):
                if not p or not p.right:
                    return
                r = p.right
                p.val, r.val = r.val, p.val
                p.n, r.n = r.n, p.n
                p.h, r.h = r.h, p.h
                p.right = r.right
                r.right = r.left
                r.left = p.left
                p.left = r

            def add(self, val):
                if not self.root:
                    self.root = self.TreeNode(val)
                    return
                def _add_work(val, p=self.root):
                    if val>p.val:
                        if not p.right:
                            p.right = self.TreeNode(val)
                        else:
                            _add_work(val, p.right)
                        if p.h<p.right.h:
                            self.right_rotate(p)
                    elif val<p.val:
                        if not p.left:
                            p.left = self.TreeNode(val)
                        else:
                            _add_work(val, p.left)
                        if p.h<p.left.h:
                            self.left_rotate(p)
                    else:
                        p.n +=1
                _add_work(val)

            def remove(self, val):
                if not self.root:
                    return
                def _remove_work(val, p=self.root, q=None):
                    if val>p.val:
                        if p.right:
                            _remove_work(val, p.right, p)
                    elif val<p.val:
                        if p.left:
                            _remove_work(val, p.left, p)
                    else:
                        if p.n>1:
                            p.n-=1
                        elif p.left and p.right:
                            x, y, p.val = p.right, None, p.right.val
                            while x.left:
                                x, y = x.left, x
                            if y:
                                y.left = x.right
                            else:
                                p.right = x.right
                        elif p.left or p.right:
                            e = p.left if p.left else p.right
                            p.val, p.left, p.right = e.val, e.left, e.right
                        else:
                            if q and q.left==p:
                                q.left = None
                            elif q:
                                q.right = None
                            else:
                                self.root = None
                _remove_work(val)
            def find(self, val):
                def _find_work(val, p=self.root):
                    if not p:
                        return False
                    if val<p.val:
                        return _find_work(val, p.left)
                    elif val>p.val:
                        return _find_work(val, p.right)
                    else:
                        return True
                return _find_work(val)
            def find2(self, val, g):
                def _find2_work(val, g, p=self.root):
                    if not p:
                        return False
                    if val-g>p.val:
                        return _find2_work(val, g, p.right)
                    elif val+g<p.val:
                        return _find2_work(val, g, p.left)
                    else:
                        return True
                return _find2_work(val, g)

            def display(self):
                def _display_work(p=self.root, dep=0):
                    if not p:
                        return
                    _display_work(p.right, dep+1)
                    print((' ')*dep+'%d:%d(%d)'%(p.val,p.n,p.h))
                    _display_work(p.left, dep+1)

                work = _display_work()
        tree = Tree()
        l = len(nums)
        for i in range(l):
            print('i=%d'%(i))
            tree.display()
            if i>0 and i>k:
                tree.remove(nums[i-k-1])
            print('---')
            tree.display()
            print('---')
            if tree.find2(nums[i], t):
                return True
            tree.add(nums[i])
        return False

# []
# 0
# 0
# nums = [-1, -1]
# k = 1
# t = 0

# nums, k, t = [1, 2], 0, 1

nums, k, t = [4, 2], 2, 1

obj = Solution()
print(obj.containsNearbyAlmostDuplicate(nums, k, t))


